package 数据结构练习.summer;

import java.util.Stack;

public class day15 {

    /*
    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    实现 MinStack 类:
    MinStack() 初始化堆栈对象。
    void push(int val) 将元素val推入堆栈。
    void pop() 删除堆栈顶部的元素。
    int top() 获取堆栈顶部的元素。
    int getMin() 获取堆栈中的最小元素。
    https://leetcode.cn/problems/min-stack
     */
    //s1存元素s2存最小值
    Stack<Integer> s1,s2;
    public day15() {
        s1=new Stack<>();
        s2=new Stack<>();
    }

    public void push(int val) {
        s1.push(val);
        if (s2.isEmpty()){
            s2.push(val);
        }else{
            if(s2.peek()>=val){
                s2.push(val);
            }
        }
    }

    public void pop() {
       int temp=s1.pop();
       if (temp==s2.peek()){
           s2.pop();
       }
    }

    public int top() {
        return s1.peek();
    }

    public int getMin() {
        return s2.peek();
    }


    /*
    给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    https://leetcode.cn/problems/valid-parentheses
     */
    public boolean isValid(String s) {
        char temp;
        Stack<Character> iu=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            temp=s.charAt(i);
            if (temp=='['||temp=='{'||temp=='('){
                iu.push(temp);
            }else {
                if (iu.isEmpty())return false;
                if (temp==']'&&iu.peek()=='['||temp=='}'&&iu.peek()=='{'||temp==')'&&iu.peek()=='('){
                    iu.pop();
                }else{
                    return false;
                }
            }
        }
        if (!iu.isEmpty()){
            return false;
        }else{
            return true;
        }
    }
}
